package leetcode.editor.vip.solution1676;

import java.util.HashSet;

public class Solution1676 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        HashSet<Integer> set = new HashSet<>();
        for (TreeNode node : nodes) {
            set.add(node.val);
        }

        return find(root, set);
    }

    private TreeNode find(TreeNode root, HashSet<Integer> set) {
        if (root == null) {
            return null;
        }

        if (set.contains(root.val)) {
            return root;
        }

        TreeNode left = find(root.left, set);
        TreeNode right = find(root.right, set);

        // 后序位置，已经知道左右子树是否存在目标值
        if (left != null && right != null) {
            // 当前节点是 LCA 节点
            return root;
        }

        return left == null ? right : left;
    }
}
